Asynchronous Transfer Mode ("ATM") is an emerging packet switching network technology designed to provide service for a wide variety of applications such as voice, video and data. Originally proposed for use in the Broadband Integrated Services Digital Network ("B-ISDN") by the International Telegraph and Telephone Consultative Committee ("CCITT"), now reorganized as the Telecommunications Standardization Sector of the International Telecommunication Union ("ITU-T"), ATM is presently moving beyond the wide area network setting into the private network arena as a platform for local area networks ("LANs") with multimedia capabilities. ATM is now well known in the art and is described in various references. E.g., Martin de Prycker, Asynchronous Transfer Mode: Solution for Broadband ISDN (2nd Ed., Ellis Horwood Ltd., West Sussex, England, 1993).
In an ATM network, as defined by the CCITT standards, information is carried in packets of fixed size, specified for B-ISDN as 53 bytes or octets, called cells. These cells are individually labelled by addressing information contained in the first 5 bytes (octets) of each cell. Although ATM evolved from Time Division Multiplexing concepts, cells from multiple sources are statistically multiplexed into a single transmission facility. Cells are identified by the contents of their headers rather than by their time position in the multiplexed stream. A single ATM transmission facility may carry hundreds of thousands of ATM cells per second originating from a multiplicity of sources and travelling to a multiplicity of destinations.
ATM is a connection-oriented technology. Rather than broadcasting cells onto a shared wire or fiber for all network members to receive, a specific routing path through the network, called a virtual circuit, is set up between two end nodes before any data is transmitted. Cells identified with a particular virtual circuit are delivered to only those nodes on that virtual circuit.
The backbone of an ATM network consists of switching devices capable of handling the high-speed ATM cell streams. The switching components of these devices, commonly referred to as the switch fabric, perform the switching function required to implement a virtual circuit by receiving ATM cells from an input port, analyzing the information in the header of the incoming cells in real-time, and routing them to the appropriate destination port. Millions of cells per second need to be switched by a single device.
Importantly, this connection-oriented scheme permits an ATM network to guarantee the minimum amount of bandwidth required by each connection. Such guarantees are made when the connection is set-up. When a connection is requested, an analysis of existing connections is performed to determine if enough total bandwidth remains within the network to service the new connection at its requested capacity. If the necessary bandwidth is not available, the connection is refused.
In order to achieve efficient use of network resources, bandwidth is allocated to established connections under a statistical multiplexing scheme. Therefore, congestion conditions may occasionally occur within the ATM network resulting in cell transmission delay or even cell loss. To ensure that the burden of network congestion is placed upon those connections most able to handle it, ATM offers multiple grades of service. These grades of service support various forms of traffic requiring different levels of cell loss probability, transmission delay, and transmission delay variance, commonly known as delay jitter. It is known, for instance, that many multimedia connections, e.g., video streams, can tolerate relatively large cell losses, but are very sensitive to delay variations from one cell to the next. In contrast, traditional forms of data traffic are more tolerant of large transmission delays and delay variance, but require very low cell losses. This variation in requirements can be exploited to increase network performance.
The ATM Forum, an organization of networking vendors, has standardized four of these grades of service, or classes of virtual circuits: constant bit rate ("CBR") circuits, variable bit rate ("VBR") circuits, available bit rate ("ABR") circuits and unspecified bit rate ("UBR") circuits. These four categories define the qualities of service available to a particular connection, and are selected when a connection is established.
A CBR virtual circuit is granted a permanent allocation of bandwidth along its entire path. The sender is guaranteed a precise time interval, or fixed rate, to send data, corresponding to the needed bandwidth, and the network guarantees to transmit this data with minimal delay and delay jitter. A CBR circuit is most appropriate for real-time video and audio multimedia streams which require network service equivalent to that provided by a synchronous transmission network. From the perspective of the source and destination, it must appear as if a virtual piece of wire exists between the two points. This requires that the transmission of each cell belonging to this data stream occur at precise intervals.
A VBR virtual circuit is initially specified with an average bandwidth and a peak cell rate. This type of circuit is appropriate for high priority continuous traffic which contains some burstiness, such as compressed video streams. The network may "overbook" these connections on the assumption that not all VBR circuits will be handling traffic at a peak cell rate simultaneously. However, although the transmission rate may vary, applications employing VBR service often require low delay and delay jitter.
An ABR virtual circuit, sometimes referred to as connection-oriented data traffic, is appropriate for network connections with uncertain requirements for throughput and delay, such as general data traffic. Currently, ABR circuits are specified with a bandwidth range, defined by a minimum bandwidth and a maximum bandwidth. It is contemplated that the actual transmission bandwidth within this range will be dynamically negotiated with the network using some form of flow control. See Flavio Bonomi and Kerry W. Fendick, "The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service," IEEE Network, March/April 1995, pp. 25-39.
A UBR virtual circuit, sometimes referred to as connectionless data traffic, is employed for the lowest priority data transmission; it has no specified associated bandwidth. The sender may send its data as it wishes, but the network makes no guarantee that the data will arrive at its destination within any particular time frame. This service is intended for applications with minimal service requirements, e.g., file transfers submitted in the background of a workstation.
A particular end-node on the network may have many virtual circuits of these varying classes open at any one time. The network interface at the end-node is charged with the task of scheduling the transmission of cells from each of these virtual circuits in some ordered fashion. At a minimum, this will entail pacing of cells from CBR circuits at a fixed rate to achieve virtual synchronous transmission. Additionally, some form of scheduling may be implemented within some or all of the switches which form the ATM network. Connections which have deviated from their ideal transmission profile as a result of anomalies in the network can be returned to an acceptable service grade.
At least two concerns are implicated in this scheduling. First, CBR traffic must be transferred at the necessary fixed rate with little or no delay jitter. Second, ideally VBR and ABR traffic should be transmitted in a manner as near as possible to their defined transfer patterns and no connection should be permitted to exceed its allocated bandwidth or peak cell rate. Although ATM networks possess other mechanisms for dealing with congestion control, adherence to the traffic contract by a source node is an important factor in overall network efficiency. See Dimitri Bertsekas & Robert Gallager, Data Networks, pp. 138-39 (2nd Ed., Prentice Hall, Englewood Cliffs, N.J., 1992).
Prior art systems exist which handle the relatively simple task of scheduling CBR traffic for transmission onto an ATM network, but these systems typically perform no scheduling of VBR and ABR traffic. For example, U.S. Pat. No. 5,390,184 to Morris discloses a scheduling mechanism for use within an ATM switch. CBR traffic is scheduled using a circular buffer containing slots corresponding to the time to transmit a single cell. Unlike VBR or ABR circuits, the bandwidth, and thus the proper cell pacing, of CBR circuits is predefined. Therefore, slots in the circular buffer are statically reserved when a CBR connection is established. The scheduler advances through the circular buffer transmitting CBR cells when a reserved slot is detected. No scheduling of other forms of traffic is performed, rather waiting VBR/ABR/UBR cells are simply transmitting during time slots not allocated for CBR traffic. Systems such as these achieve proper pacing of synchronous data streams, but do not serve to maintain VBR/ABR data streams in compliance with their negotiated traffic contracts.
The lack of a scheduling mechanism for VBR and ABR circuits within an end-node network interface, places a burden upon applications themselves to generate data at appropriate rates for the network implementation. Requiring applications to perform pacing of VBR/ABR streams may be permissible when such applications have been designed with an ATM network connection in mind. However, such solutions are increasingly unacceptable as ATM moves into the LAN setting. Applications designed for conventional LAN technologies cannot be conveniently adapted to produce data under defined pacing conditions; rather, these applications are likely to transmit data without concern for network congestion conditions. If no pacing of these streams is performed, congestion caused by bursty VBR/ABR streams may impair network performance unless the network itself takes other measures to police transmissions. Of course, a simple method to prevent such network congestion is to request an amount of bandwidth much greater as that which can be reasonably expected to be required at any time by a particular application. This solution, however, leads to an underutilization of the network and an inefficient allocation of resources.
Therefore, there persists a need for a cell pacing mechanism capable of producing uniform transmission of ABR, VBR and UBR data streams, as well as CBR streams. Such a system would provide fixed rate pacing of CBR streams while simultaneously policing and shaping VBR, ABR and UBR data traffic.